package com.company.回溯;

import java.util.ArrayList;
import java.util.List;

public class Leet46 {
    private static int[] nums;
    /*
     * path为路径，记录当前状态，需要回溯
     * i也可看作path当前的长度
     * visited记录访问情况
     * 遍历visited中未访问的
     */
    private void dfs(List<List<Integer>> ans,List<Integer> path,boolean[] visited,int i){
        //边界条件
        if(i==nums.length){
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int j = 0; j < nums.length; j++) {
            //选过就跳过
            if(visited[j])
                continue;
            //必须选一个
            // path.add和path.remove可以优化成一个path.set(i, nums[j]);
            path.add(nums[j]);
            visited[j] = true;
            dfs(ans,path,visited,i+1);
            //回溯
            path.remove(path.size()-1);
            visited[j] = false;
        }
        return;
    }
    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<>();
        boolean[] visited=new boolean[nums.length];
        dfs(ans,path,visited,0);
        return ans;
    }
}
